1. Field of the Invention
The present invention relates to a dichotomy determination graph for representing a logical function, and more specifically to a variable sequence determining method used in generating a dichotomy determination graph for representing a logical function of a two-step logical circuit.
2. Description of the Related Art
Efficient representation of a logical function using a computer is very important in various logical design supporting technologies such as logical collating, logical verification, logical circuit simplification, test circuit generation, etc. Of these techonologies, the logical collating and logical circuit simplification occupy the most important part.
Computer representation of a logical function includes a truth value table, a logical expression in the sum-of-products format, and a dichotomy determination graph. A dichotomy determination graph can represent a large logical function if an appropriate variable sequence is assigned when the graph is generated. The dichotomy determination graph can simplify the representation of a logical function by sharing a sub-graph through fixing for all paths a variable sequence in a determination tree (originally a tree, but can be a shared graph). Additionally, it can be normalized, that is, logical functions can indicate the same result when represented in a dichotomy determination graph if the original logic is the same.
FIG. 1 (PRIOR ART) shows a sample of a dichotomy determination graph. FIG. 1 shows a logical function X.sub.1 .times.X.sub.2 +X.sub.3 (X.sub.3 is the negative of X.sub.3). In FIG. 1, each circle indicates a node corresponding to a variable. 1 corresponds to X.sub.1. Each square corresponds to a logical function value. When a square contains the numerical character 1, it indicates that the logical function value is 1. For example, when X.sub.1 is 0, an edge with the symbol 0 is searched. When X.sub.1 is 1, an edge with the symbol 1 is searched. If a square containing 0 is searched and found finally, the logical function value is 0. The sequence of flexibly arranged variables is fixed for each path, a graph can be shared, and a logical function can be represented as a result. That is, in FIG. 1, the node of variable X.sub.3 is pointed to by two edges and is shared.
A logical function can be simplified and represented in a dichotomy determination graph as shown in FIG. 1. However, a graph can be greatly changed depending on the sequence of flexibly arranged variables. This problem is explained in association with FIGS. 2 and 3.
FIGS. 2 and 3 show the same logical function X.sub.1 .times.X.sub.2 +X.sub.3 .times.X.sub.4 +X.sub.5 .times.X.sub.6. However, if the sequence of flexibly arranged variables is appropriately fixed as shown in FIG. 2 (PRIOR ART), X.sub.1, X.sub.2, X.sub.3, X.sub.4, X.sub.5, and X.sub.6, the dichotomy determination graph is greatly simplified. By contrast, if the sequence of flexibly arranged variables is fixed as shown in FIG. 3 (PRIOR ART), X.sub.1, X.sub.3, X.sub.5, X.sub.2, X.sub.4, and X.sub.6, the dichotomy determination graph is generated in a much larger size.
Therefore, a dichotomy determination graph greatly depends on the sequence of flexibly arranged variables. In a dichotomy determination graph having a large number of variables, the optimum sequence of variables must be determined by a heuristic approach. A method of determining a comparatively appropriate sequence of variables has been established for a multiple-step circuit. However, the method doesn't work well for a two-step circuit.